#pragma once

#include <vector>
#include <list>
#include <iomanip>//输出控制必备的头文件

using namespace std;

//图公共接口
class Vertex {
    int value;
};

struct Edge {
	int v1;
	int v2;
	int w;
};

class Graph {
public:
    Graph(int v) : m_nv(v), m_ne(0) {}      // 创建含有v个顶点但不含边的图
    int V() const {return m_nv;}      // 顶点数
    int E() const {return m_ne;}      // 边数
    virtual bool AddEdge(int v1, int v2, int w = 0) = 0;   // 向图中添加边v-w
	virtual int Weight(int v1, int v2);	  // v1和v2之间的边的权重
    virtual vector<int> Adj(int v) = 0;       // 和v相邻的所有顶点
	virtual void Show() = 0;		// 打印该图
	virtual vector<Edge> getAllEdge() { return m_ve; }

protected:
    int m_nv;      // 顶点数
    int m_ne;      // 边数
    vector<Edge> m_ve;
};

//邻接矩阵表示法
class ArrGraph : public Graph {
public:
    ArrGraph(int v);
    int IndexVex(int ver);
	bool AddEdge(int v1, int v2, int w = 0);
	vector<int> Adj(int v);
	void Show();

private:
    vector<int> vexs;        //顶点表
    vector<vector<int>> arcs;   // 邻接矩阵
};

//邻接链表表示法

//邻接链表
struct VertexNode {
    int ver;
    VertexNode *next;
};
class ListGraph : public Graph {
public:
    ListGraph(int v);
    int IndexVex(int ver);
    bool AddEdge(int v1, int v2, int w = 0);
    vector<int> Adj(int v);
    void Show();

private:
    vector<list<int>> m_vAdj;
};

//有向图
class Digraph : public ArrGraph {
public:
	Digraph(int v);
	bool AddEdge(int ver);
    //从v出发可达的边
	vector<int> Adj(int v);
}; 
